#ifndef GUARD_MINHA_MATRIZ_ESPARSA_H
#define GUARD_MINHA_MATRIZ_ESPARSA_H
/*
TRABALHO 1 de COMPUTACAO 3 2007/2
Alunos:
 Anderson Marinho (DRE: 104042916)
 Artur Souza (DRE: 104020972)
*/

#include <iostream>
#include "minha_matriz_exceptions.h"
#include <iterator>
#include <map>
#include <set>

using namespace std;

template<class I, class T> class minha_matriz_esparsa;

template<class I, class T> class minha_matriz_esparsa_linha {
private:
	I l;
	map<I,T> * line;
public:
	minha_matriz_esparsa_linha(I _l, map<I,T> * _line) :
		l(_l), line(_line) {
	}
	T& operator[](I c) const {
		return (*line)[c];
	}
	I getLin() const {
		return l;
	}

	friend ostream& operator <<(ostream& o,
			const minha_matriz_esparsa_linha<I,T>& mml) {
		int first = 1;
		typedef typename map<I,T>::const_iterator Iterator;
		for (Iterator itr = (*mml.line).begin(); itr != (*mml.line).end(); itr++) {
			o << (!first ? " " : "")<< "("<< mml.getLin() << ","<< itr->first
					<< ")="<< itr->second;
			first = 0;
		}
		return o;
	}

};

template<class I, class T> class minha_matriz_esparsa_coluna {
private:
	I c;
	minha_matriz_esparsa<I,T> * m;
	map<I, map<I,T> > * mp;
public:
	minha_matriz_esparsa_coluna(I _c, minha_matriz_esparsa<I,T> * _m, map<I, map<I,T> > * _mp) :
		c(_c), m(_m), mp(_mp) {
	}
	T& operator()(I l) const {
		return (*m)(l, c);
	}
	T& operator[](I l) const {
		return (*m)(l, c);
	}
	int getLin() const {
		return (*m).getLin();
	}
	I getCol() const {
		return c;
	}

	friend ostream& operator <<(ostream& o,
			minha_matriz_esparsa_coluna<I,T>& mmc) {
		int first = 1;
		typedef typename map<I,map<I,T> >::const_iterator Iterator;
		for (Iterator itr = (*mmc.mp).begin(); itr != (*mmc.mp).end(); itr++) {
			if ((itr->second).count(mmc.c) > 0) {
				o << (!first ? " " : "")<< "("<< itr->first << ","<< mmc.c
					<< ")="<< (*(mmc.m))(itr->first,mmc.c);
				first = 0;
			}
		}
		return o;
	}

};

template<class I, class T> class minha_matriz_esparsa {
private:
	map<I,map<I,T> > m;
	int lin;
	int col;
	set<I> idxCol;
	int n;

public:
	int getLin() const {
		return lin;
	}

	int getCol() const {
		return col;
	}

	double utilizacao() const {
		return (n*1.0)/(lin*col*1.0);
	}

	minha_matriz_esparsa(int n = 3) :
		lin(n), col(n), n(0) {
	}

	minha_matriz_esparsa(int _lin, int _col) :
		lin(_lin), col(_col), n(0) {
	}

	~minha_matriz_esparsa() {
	}

	T& operator()(const I i, const I j) {
		if (m.count(i) == 0) {
			if (m.size() == lin) {
				throw ExcecaoIndiceInvalidoDeMatriz();
			}
		}
		if (idxCol.count(j) == 0) {
			if (idxCol.size() == col) {
				throw ExcecaoIndiceInvalidoDeMatriz();
			}
			idxCol.insert(j);
		}
		if (m[i].count(j) == 0) {
			n++;
		}
		return m[i][j];
	}

	friend minha_matriz_esparsa<I,T> operator +(minha_matriz_esparsa<I,T>& mm1,
			minha_matriz_esparsa<I,T>& mm2) {
		minha_matriz_esparsa<I,T> mm(mm1.lin, mm1.col);
		if (mm1.lin != mm2.lin|| mm1.col != mm2.col)
			throw ExcecaoSomaMatrizesDiferentes();
		for (I i = 0; i < mm.lin; i++) {
			for (I j = 0; j < mm.col; j++) {
				mm(i, j) = mm1(i,j) + mm2(i,j);
			}
		}
		return mm;
	}

	friend minha_matriz_esparsa<I,T> operator *(minha_matriz_esparsa<I,T>& mm1,
			minha_matriz_esparsa<I,T>& mm2) {
		minha_matriz_esparsa<I,T> mm(mm1.lin, mm2.col);
		if (mm1.col != mm2.lin)
			throw ExcecaoMultiplicacaoInvalidaDeMatrizes();

		for (I i = 0; i < mm1.lin; i++) {
			for (I j = 0; j < mm2.col; j++) {
				for (I k = 0; k < mm2.lin; k++) {
					mm(i, j) = mm(i,j) + mm1(i,k) * mm2(k,j);
				}
			}
		}
		return mm;
	}

	minha_matriz_esparsa<I,T>& operator =(const minha_matriz_esparsa<I,T>& mm2) {
		lin = mm2.lin;
		col = mm2.col;
		m = mm2.m;
		return *this;
	}

	minha_matriz_esparsa_coluna<I,T> operator ()(I c) {
		return minha_matriz_esparsa_coluna<I, T>(c, this, &m);
	}

	minha_matriz_esparsa_linha<I,T> operator [](const I l) {
		return minha_matriz_esparsa_linha<I, T>(l, m[l]);
	}

	friend ostream& operator <<(ostream& o, minha_matriz_esparsa<I,T>& mm) {
		typedef typename map<I, map<I,T> >::const_iterator Iterator;
		typedef typename map<I,T>::const_iterator Iterator2;
		Iterator itr = mm.m.begin();
		for (Iterator itr = mm.m.begin(); itr != mm.m.end(); itr++) {
			int first = 1;
			for (Iterator2 itr2 = (itr->second).begin(); itr2 != (itr->second).end(); itr2++) {
				o << (!first ? " " : "")<< "("<< itr->first<< ","<< itr2->first
						<< ")="<< itr2->second;
				first = 0;
			}
			o << endl;
		}
		return o;
	}

	class Iterator : public std::iterator<std::forward_iterator_tag, T> {
public:
		Iterator(minha_matriz_esparsa<I,T>* _m, int lin=0, int col=0) :
			itM(_m), itNLin(lin), itNCol(col) {
		}
		~Iterator() {
		}

		bool operator!=(const Iterator& other) {
			return (itNLin != other.itNLin);
		}

		Iterator& operator++() {
			itNCol = (itNCol+1)%itM->col;
			if (!itNCol)
				itNLin++;
			return (*this);
		}

		T operator*() {
			return (*itM)(itNLin, itNCol);
		}

private:
		minha_matriz_esparsa<I,T>* itM;
		int itNLin, itNCol;
	};

	class IteradorLinha : public std::iterator<std::forward_iterator_tag, T> {
public:
		IteradorLinha(map<int,map<int,int> >::iterator _it) :
			it(_it) {
		}
		~IteradorLinha() {
		}

		bool operator!=(const IteradorLinha& other) {
			return (it != other.it);
		}

		IteradorLinha& operator++() {
			it++;
			return (*this);
		}

	    minha_matriz_esparsa_linha<I,T> operator*() {
			return minha_matriz_esparsa_linha<I, T>(it->first, &(it->second));
		}

private:
		typename map<I,map<I,T> >::iterator it;
	};

	class IteradorColuna : public std::iterator<std::forward_iterator_tag, T> {
public:
		IteradorColuna(typename set<I>::iterator _it, minha_matriz_esparsa<I,T>* _m) :
			it(_it), mme(_m) {
		}
		~IteradorColuna() {
		}

		bool operator!=(const IteradorColuna& other) {
			return (it != other.it);
		}

		IteradorColuna& operator++() {
			it++;
			return (*this);
		}

		minha_matriz_esparsa_coluna<I,T> operator*() {
			return minha_matriz_esparsa_coluna<I, T>(*it, mme, &(mme->m));
		}

private:
		typename set<I>::iterator it;
		minha_matriz_esparsa<I,T>* mme;
	};

	Iterator begin() {
		return (Iterator(this));
	}

	Iterator end() {
		return (Iterator(this, lin, col));
	}

	IteradorLinha beginLinha() {
		return (IteradorLinha(this->m.begin()));
	}

	IteradorLinha endLinha() {
		return (IteradorLinha(this->m.end()));
	}

	IteradorColuna beginColuna() {
		return (IteradorColuna(this->idxCol.begin(), this));
	}

	IteradorColuna endColuna() {
		return (IteradorColuna(this->idxCol.end(), this));
	}

};

#endif
